--https://www.lua.org/pil/11.4.html

local Q = @@CLASS("Queue")

Q.first, Q.last = 0, -1

@@EXTEND(Q,
	 {
	    @@SFN(push_left, v,
		  local first = self.first - 1
		  self.first = first
		  self[first] = v),

	    @@SFN(push_right, v,
		  local last = self.last + 1
		  self.last = last
		  self[last] = v),

	    @@SFN(pop_left,
		  local first = self.first
		  @@ASSERT(first <= self.last)
		  local value = self[first]
		  self[first] = nil
		  self.first = first + 1
		  return value),

	    @@SFN(pop_right,
		  local last = self.last
		  @@ASSERT(last >= self.first)
		  local value = self[last]
		  self[last] = nil
		  self.last = last - 1
		  return value)
	    
	})

return Q
